\section{Previous work}

We will frequently refer to techniques used by \sbcl{} because of its
reputation as a high-performance implementation.  We will however also
use other high-performance implementations for comparison when we have
information on the techniques used by those implementations, or when
we can reasonably guess these techniques from other evidence.

For its implementation of \texttt{find}, \sbcl{} takes advantage of
the freedom given by the standard, by processing elements from the
beginning, and remembering the last element that satisfies the test.
For implementations where the technique is unknown, it suffices to
write a test function that counts the number of times it is invoked
and run it on a list where only the last element satisfies the test.

For its implementation of \texttt{count}, \sbcl{} uses the simple
technique of reversing the list first and then processing the elements
of the reversed list from the beginning.

%% To test the stack depth of various implementations, we devised the
%% following test:

%% {\small\begin{verbatim}
%% (defun stack-depth (n)
%%   (declare (optimize (space 3)))
%%   (if (zerop n) 0 (1+ (stack-depth (1- n)))))
%% \end{verbatim}}

%% The following table shows approximate values of the argument to
%% \texttt{stack-depth} for which some implementations exhaust the stack:

%% \FIXME{with default stack and heap size. Irene}

%% \begin{tabular}{|l|r|}
%% \hline
%% Implementation & argument\\
%% \hline
%% \hline
%% \sbcl{} & 90000\\
%% \hline
%% Allegro & ???\\
%% \hline
%% LispWork & ???\\
%% \hline
%% \end{tabular}

As we already mentioned, we use recursion as the basis of our
technique, because it is quite fast.  We devised the following test to
verify this hypothesis:

{\small
\begin{verbatim}
(defun recursive-count (x list)
  (declare (optimize (speed 3) (debug 0) (safety 0)))
  (if (endp list)
      0
      (+ (recursive-count x (cdr list))
           (if (eq (car list) x) 1 0))))
\end{verbatim}
}

On \sbcl{} executing this function on a list with $50000$ elements
where no element satisfies the test takes around $4$ns per element
compared to around $1.5$ns for an explicit loop from the beginning of
the list, and around twice as fast as calling \texttt{count}.  This
result indicates that we should use recursion whenever the size of the
stack allows it, though there is of course no portable way of testing
how much stack space is available.  However, each implementation might
have a specific way, which would then be good enough.
